package everydayone.threepartsequalsum;
/**
 * @Date 2020/03/11
 * @author 王光浩
 * @Thinking 先求出数组所有元素的总和，将其等分为3份，然后对数组进行遍历，判断是否能够找到连续的3份值。
 * @Analysis 时间复杂度O（2n），空间复杂度O（1）
 */
public class MyMethodOne {
    public boolean canThreePartsEqualSum(int[] A) {
    	if(A.length<3)return false;
    	//数组元素的总和
    	int sum=0;   
    	for(int i:A)
    		sum+=i;
    	if(sum%3!=0)return false;
    	int part=sum/3;   //如果能够等分数组，则每份数组的总和
    	//判断是否存在3个连续、互不相交的子数组将数组等分、
    	int count=0;  //计数器，统计相加值为part的子数组个数
    	int total=0;
    	for(int i=0;i<A.length;i++) {
    		total+=A[i];
    		//每发现一个总和等于part的子数组，count加一，total清零
    		if(total==part) {
    			total=0;
    			count++;
    		}
    		//如果已经找到两个，同时数组没有遍历完，则一定可以分成三等分，否则不可以
    		if(count==2) {
    			if(i!=A.length-1)return true;
    			else return false;
    		}
    		
    	}
    	return false;
    }
}
